#pragma once

#include <metalc/mlayer/_mlayer.h>
#include <dbg.h>
#include <metalc/block/cobj.h>
/* buddy算法，二进制伙伴系统，利用duff's device进行loops unroll？
	输入:
	- [size 范围]
	- [sync 同步方式]
	外部或内部meta管理方式? 内部meta必须使用扫描合并式，外部使用flatmap之类的 
*/
/* 输入锁 */
#ifndef BINBUDDY_APDS
	#define BINBUDDY_APDS			sffwd
#endif

/* 直接定义锁和同步函数，这样就不用通过DEF定义宏函数方式传入 */
MLAYER_SYNC(buddy, BINBUDDY_APDS);

#define BUDDY_PRINT(...)		INFO(__VA_ARGS__)
// #define BUDDY_PRINT(...)		dbg_printf(__VA_ARGS__)

/* 定义输入和输出 */
OU2INFUN(cls, buddy_cls)
OU2INFUN(cobj, buddy_cobj)
OU2INFUN(apds, buddy_apds)

typedef struct buddy_obj
{
	buddy_apds_t apds_obj;
	// word_t total_size;
	dlist_t buddyflist[];
} buddy_obj_t;

typedef const struct buddy_conf {
	const size_t min_size;
	const size_t oom_allocsize;
	const size_t total_szcls;
} buddy_conf_t;

/* 定义三个临界区 */
STA_INFUN(buddy_critsec)
uvoid*	(* const find_split)(buddy_obj_t *bsheap, szcls_t szcls, size_t align_size);
uvoid*	(* const try_split)(buddy_obj_t *bsheap, void *mem, size_t cur_size, szcls_t cur_cls, szcls_t request_cls);
void *	(* const free_merge)(buddy_obj_t *bsheap, void *mem, size_t size, szcls_t szcls, hword_t nr);
END_INFUN(buddy_critsec)

SAI uvoid *__binbuddy_try_split(buddy_obj_t *bsheap, void *mem, size_t cur_size, szcls_t cur_cls, szcls_t request_cls, INFUN(buddy_cobj, cobj))
{
	ASSERT(cur_cls >= request_cls);
	// ASSERT(cur_cls != 0);
	cobj_t *rest = NULL;
	while (cur_cls > request_cls)
	{
		// 拆分一半,修改size,
		cur_cls -= 1;
		void *rest = cobj->split(mem, cur_size, cur_size >> 1, FALSE);
		/* 记录大小以便合并时检查 */
		dlist_t *node = cobj->set_cobj(rest, cur_size >> 1, 0);
		// dlist_t *node = (dlist_t *)cobj->ptr2uptr(rest);
		ASSERT(rest);
		// debug_fprintf(stderr, "[pgbuddy] split inserted %lx, size%lx\n", rest, size);
		BUDDY_PRINT("[binbuddy] %p split %p, size %lx inserted to %x\n", mem, rest, cur_size >> 1, cur_cls);
		
		dlist_add_head(&bsheap->buddyflist[cur_cls], node);
		cur_size = cur_size >> 1;
	}
	// dbg_printf(set_cobj)
	// TODO: 内部维护的无需pmap映射??似乎是这样的
	/* printf("[binbuddy] set cobj used %p, size %lx\n", mem, cur_size); */
	BUDDY_PRINT("[binbuddy] set cobj used %p, size %lx, request %u\n", mem, cur_size, request_cls);
	return cobj->set_cobj(mem, cur_size, 1);
}
SAI uvoid *__binbuddy_find_split(buddy_obj_t *bsheap, szcls_t szcls, size_t align_size, const szcls_t total_clsnr, INFUN(buddy_cls, cls), INFUN(buddy_cobj, cobj)){
	/* 这不需要 */
	PARAM_USED(align_size);

	dlist_t *node = NULL_PTR;
	/* 向上搜索队列 */
	szcls_t cidx;
	for (cidx = szcls; cidx < total_clsnr + 1; cidx++){
		dlist_t *cur_list = &bsheap->buddyflist[cidx];
		if (!list_is_empty(cur_list)){
			/* 删除节点 */
			node = cur_list->next;
			dlist_del(cur_list, node->next);
			break;
		}
	}
	if (!node) return NULL_PTR;

	void *nmem = cobj->uptr2ptr(node);
	/* 尝试分裂 */
	// if (cidx >= szcls) {
	// 	/* */
	// }
	// __binbuddy_try_split(bsheap, nmem, cls->cls2sz(cidx), cidx, szcls, cobj);
	// BUDDY_PRINT("[binbuddy] set cobj used %p, size %lx\n", nmem, align_size);
	/* printf("[%x][binbuddy] alloc %p, size %lx\n", mtls_get()->apdstls.tinfo.tid, nmem, align_size); */
	// bsheap->total_size -= align_size;
	return __binbuddy_try_split(bsheap, nmem, cls->cls2sz(cidx), cidx, szcls, cobj);
}

SAI void *__binbuddy_free_merge(buddy_obj_t *bsheap, void *mem, size_t size, szcls_t szcls, const size_t max_size, const szcls_t total_clsnr, INFUN(buddy_cobj, cobj)){
	void *cur = mem;
	void *buddy;
	dlist_t *node;
	size_t rsize;
	cobj->set_cobj(mem, size, 0);
	BUDDY_PRINT("[binbuddy] free %p, size %lx, try merging...\n", cur, size);
	/* printf("[%x][binbuddy] free %p, size %lx, try merging...\n", mtls_get()->apdstls.tinfo.tid, cur, size); */
	while (szcls < total_clsnr){
		buddy = (void *)((paddr_t)cur ^ size);
		node = (dlist_t *)cobj->ptr2uptr(buddy);
		/* 互相合并 */
		if ((paddr_t)cur & size) {
			rsize = cobj->merge_next(buddy, size);
			/* 无法合并 */
			if (rsize == size) break;
			/* 合并成功 */
			cur = buddy;
		}
		else {
			rsize = cobj->merge_next(cur, size);
			/* 无法合并 */
			if (rsize == size) break;
		}
		// cobj->set_cobj(buddy, 0, 0);
		BUDDY_PRINT("[binbuddy] %p merge %p, size %lx\n", cur, buddy, rsize);
		/* fprintf(stderr, "[binbuddy] %p merge %p, size %lx, remove %p -x- %p -x- %p\n", cur, buddy, rsize, node->prev, node, node->next); */
		__dlist_del(node);
		szcls += 1;
		size += size;
	}

	if (szcls == total_clsnr)
	{
		/* 尝试lazy decommit */
		BUDDY_PRINT("[binbuddy] try decommited %p, %lx\n", cur, size);
		PARAM_USED(max_size);
		/* os_decommit_lazy(cur, max_size, 1); */
		os_decommit_dontneed((void *)((paddr_t)cur + PAGE_SIZE), max_size - PAGE_SIZE);
		/* return cur; */
	}

	/* 将合并完成的内存块插入队列 */
	// debug_fprintf(stderr, "[pgbuddy] inserted [%p, %lx]\n", cur, get_sz_bycls_pgbuddy(cls));
	BUDDY_PRINT("[binbuddy] merged node %p, size %lx inserted to %x\n", cur, size, szcls);
	node = (dlist_t *)cobj->ptr2uptr(cur);
	
	dlist_add_head(&bsheap->buddyflist[szcls], node);

	return NULL;
}

/* 宏函数用于转换成临界区形式 */
#define DEF_BUDDY_CRTISEC(name, cobj_comp, cls_comp, apds_comp, TOTALCLS_NR, MAX_SIZE)		\
/* 构造find split的临界区 */\
SAI uvoid *name##_binbuddy_find_split(buddy_obj_t *bsheap, szcls_t szcls, size_t align_size){\
	return __binbuddy_find_split(bsheap, szcls, align_size, TOTALCLS_NR, OUFUN_OF(cls_comp), OUFUN_OF(cobj_comp));\
}\
static apdsret_t name##_find_split_crit(APDSFUNC_ARGLIST){\
	buddy_obj_t *bsheap = (buddy_obj_t *)arg0;\
	szcls_t szcls = (szcls_t)arg1;\
	size_t align_size = (size_t)arg2;\
	PARAM_USED(arg3);\
	return (apdsret_t)name##_binbuddy_find_split(bsheap, szcls, align_size);\
}\
/* 构造try split的临界区 */\
SAI uvoid *name##_binbuddy_try_split(buddy_obj_t *bsheap, void *mem, size_t cur_size, szcls_t cur_cls, szcls_t request_cls){\
	return __binbuddy_try_split(bsheap, mem, cur_size, cur_cls, request_cls, OUFUN_OF(cobj_comp));\
}\
static apdsret_t name##_try_split_crit(APDSFUNC_ARGLIST){\
	buddy_obj_t *bsheap = (buddy_obj_t *)arg0;\
	void *mem = (void *)arg1;\
	size_t cur_size = (size_t)arg2;\
	szcls_t cur_cls = (szcls_t)word_high(arg3);\
	szcls_t request_cls = (szcls_t)word_low(arg3);\
	return (apdsret_t)name##_binbuddy_try_split(bsheap, mem, cur_size, cur_cls, request_cls);\
}\
/* 构造free_try_merge的临界区 */\
SAI void* name##_binbuddy_free_merge(buddy_obj_t *bsheap, void *mem, size_t size, szcls_t szcls, hword_t nr){\
	slist_t *cur = (slist_t *)mem;\
	BUDDY_PRINT("[binbuddy] try free nr %x\n", nr);\
	for (word_t idx = 0; idx < nr; idx++){\
		slist_t *next = cur->next;\
		__binbuddy_free_merge(bsheap, cur, size, szcls, MAX_SIZE, TOTALCLS_NR, OUFUN_OF(cobj_comp));\
		cur = next;\
	}\
	return NULL_PTR;\
}\
static apdsret_t name##_free_merge_crit(APDSFUNC_ARGLIST){\
	buddy_obj_t *bsheap = (buddy_obj_t *)arg0;\
	void *mem = (void *)arg1;\
	size_t size = (size_t)arg2;\
	szcls_t szcls = (szcls_t)word_high(arg3);\
	hword_t nr = (szcls_t)word_low(arg3);\
	return (apdsret_t)name##_binbuddy_free_merge(bsheap, mem, size, szcls, nr);\
}\
SAI uvoid* name##_find_split(buddy_obj_t *bsheap, szcls_t szcls, size_t align_size){\
	/* INFUN(buddy_apds, apdsf) = OUFUN_OF(apds_comp); */\
	BUDDY_PRINT("[binbuddy] apds run %s\n", TO_STRING(name##_find_split));\
	APDS_ARGS(apdsarg, bsheap, szcls, align_size, NULL_PTR);\
	return (uvoid*)(OUFUN_OF(apds_comp))->sync(&bsheap->apds_obj, name##_find_split_crit, apdsarg);\
}\
SAI uvoid* name##_try_split(buddy_obj_t *bsheap, void *mem, size_t cur_size, szcls_t cur_cls, szcls_t request_cls){\
	/* INFUN(buddy_apds, apdsf) = OUFUN_OF(apds_comp); */\
	BUDDY_PRINT("[binbuddy] apds run %s\n", TO_STRING(name##_try_split));\
	APDS_ARGS(apdsarg, bsheap, mem, cur_size, new_word(cur_cls, request_cls));\
	return (void*)(OUFUN_OF(apds_comp))->sync(&bsheap->apds_obj, name##_try_split_crit, apdsarg);\
}\
SAI void* name##_free_merge(buddy_obj_t *bsheap, void *mem, size_t size, szcls_t szcls, hword_t nr){\
	/* INFUN(buddy_apds, apdsf) = OUFUN_OF(apds_comp); */\
	BUDDY_PRINT("[binbuddy] apds run %s\n", TO_STRING(name##_free_merge));\
	APDS_ARGS(apdsarg, bsheap, mem, size, new_word(szcls, nr));\
	return (void*)(OUFUN_OF(apds_comp))->sync(&bsheap->apds_obj, name##_free_merge_crit, apdsarg);\
}\
NEW_INFUN(buddy_critsec, name##_critsec, name##_find_split, name##_try_split, name##_free_merge)

/* 定义参数 */

SAI buddy_obj_t *__binbuddy_init(void *bsmem, size_t size, const szcls_t total_clsnr, INFUN(buddy_apds, apdsf)){
	// ASSERT(is_powerof2(min_size) && is_powerof2(max_size));
	ASSERT(size >= sizeof(buddy_obj_t) + (total_clsnr + 1) * sizeof(dlist_t));
	buddy_obj_t *bsheap = (buddy_obj_t *)bsmem;
	word_t dlist_len = (total_clsnr + 1);
	// bsheap->total_size = 0;
	for(word_t idx = 0; idx < dlist_len; idx++){
		dlist_init(&bsheap->buddyflist[idx]);
	}
	apds_t *ret = apdsf->init(&bsheap->apds_obj, sizeof(bsheap->apds_obj));
	BUDDY_PRINT("[binbuddy] init apdsf %p, size %lx\n", ret, (size_t)sizeof(bsheap->apds_obj));
	ASSERT(ret);
	return bsheap;
}

SAI void _binbuddy_pinit(const mlfunc_t * cont){
	PARAM_USED(cont);
	BUDDY_PRINT("_binbuddy pinit\n");
}
SAI void _binbuddy_tinit(const mlfunc_t * cont, buddy_obj_t *buddy){
	mtls_t *tls = mtls_get();
	tls->objs[cont->lidx] = buddy;
	BUDDY_PRINT("_binbuddy tinit heap: %p\n", buddy);
}




SAI void *_binbuddy_oomhandler(mreq_t *req, const mlfunc_t * cont, size_t min_allocsize)
{
	void *ret;
	if (req->size < min_allocsize) {
		req->size = min_allocsize;
	}
	req->nr = 1;
	ret = cont->lalloc(req);
	BUDDY_PRINT("[binbuddy] oom, alloc %p, size %lx, %lx\n", req->ptr, req->size, req->align);
	// dbg_printf("[binbuddy] oom, try alloc %lx, %lx\n", req->size, req->align);
	return ret;
}


SAI UNROLL_LOOPS void *_binbuddy_alloc(mreq_t *req, const mlfunc_t * cont, buddy_obj_t *bsheap, buddy_conf_t *conf, \
 INFUN(buddy_cls, cls), INFUN(buddy_cobj, cobj), INFUN(buddy_critsec, critsec)){
	
	/* 超过大小，跳到下一级 */
	size_t req_size = req->size;
	if (MLAYER_INVALID_REQSZ(cont, req_size)) return cont->lalloc(req);
/* 	mtls_t *tls = mtls_by_req(req);
	buddy_obj_t *bsheap = (buddy_obj_t *)tls->objs[cont->lidx]; */
	mtls_t *tls = mtls_by_req(req);
	ASSERT(tls);
	ASSERT(bsheap);

	if (req->align > conf->min_size){
		/* 大2倍方式确保对齐 */
		req_size = align_up(req_size + cobj->mocupysz(), req->align << 1);
	}else{
		req_size = align_up(req_size + cobj->mocupysz(), conf->min_size);
	}

	szcls_t szcls = cls->sz2cls(req_size);
	size_t aligned_size = cls->cls2sz(szcls);
	BUDDY_PRINT("[binbuddy] try alloc size %lx, szcls %u, aligend size %lx\n", req_size, szcls, aligned_size);
	
	/* 加锁 */
	uvoid *ret = critsec->find_split(bsheap, szcls, aligned_size);
	// void *ret = _binbuddy_find_split(bsheap, szcls, aligned_size, total_clsnr, cls, cobj);
	/* 释放锁 */

	if (!ret){
		/* 向上层请求 */
		// mreq_t req;
		req->size = aligned_size;
		void *newmem = _binbuddy_oomhandler(req, cont, conf->oom_allocsize);
		if (!newmem) return NULL_PTR;
		/* 加锁 */
		// bsheap->total_size += cont->lmaxsize - aligned_size;
		// ret = _binbuddy_try_split(bsheap, newmem, cont->lmaxsize, total_clsnr, szcls, cobj);
		ASSERT(is_powerof2(req->size));
		ASSERT(is_ptr_aligned(newmem, conf->min_size));
		ret = critsec->try_split(bsheap, newmem, req->size, cls->sz2cls(req->size), szcls);
		/* 释放锁 */
		// BUDDY_PRINT("[binbuddy] set cobj used %p, size %lx\n", newmem, aligned_size);
		ASSERT(ret);
	}
	ASSERT(req->align == 0 || is_ptr_aligned(ret, req->align));
	// if (!is_ptr_aligned(ret, conf->min_size)){
	// 	fatal("should be aligned %p %lx\n", req->ptr, aligned_size);
	// }

	BUDDY_PRINT("[binbuddy]" PRINC(RED, "allocated") " %p, req_size %lx, size %lx, cls %u\n", ret, req_size, aligned_size, szcls);
	ASSERT(ret);
	req->ptr = cobj->uptr2ptr(ret);
	/* printf("[%u][alloc %p]\n", mtls_by_req(req)->apdstls.tinfo.tid, ret); */
	
	return ret;	
}

SAI bool_t _binbuddy_free(mreq_t *req, const mlfunc_t * cont, buddy_obj_t *bsheap, \
INFUN(buddy_cls, cls), INFUN(buddy_cobj, cobj), INFUN(buddy_critsec, critsec)){
	PARAM_USED(cobj);
	size_t msize = req->size;
	
	/* 下一级 free */
	if (MLAYER_INVALID_REQSZ(cont, msize)) return cont->lfree(req);
	
	mtls_t *tls = mtls_by_req(req);
	ASSERT(tls);
	ASSERT(bsheap);
	ASSERT(is_powerof2(msize));
	szcls_t szcls = cls->sz2cls(msize);

	BUDDY_PRINT("[binbuddy] try free %p, size %lx, szcls %u\n", req->ptr, msize, szcls);
	/* 加锁 */
	/* 多余的会被释放 */
	// slist_t *cur = req->ptr;
	// for (word_t idx = 0; idx < req->nr; idx++){
	// 	slist_t *next = cur->next;
	// 	_binbuddy_free_merge(bsheap, (void *)cur, msize, szcls, cont, total_clsnr, cobj);
	// 	cur = next;
	// }
	
	// __DEBUG_ASSERT_DOSTH(is_aligned(msize, cls->cls2sz(0)), dbg_printf("err size %lx\n", msize));
	critsec->free_merge(bsheap, req->ptr, msize, szcls, req->nr);
	/* 释放锁 */
	BUDDY_PRINT("[binbuddy]" PRINC(YELLOW, "freed") " %p, size %lx, cls %u\n", req->ptr, msize, szcls);
	return TRUE;
}

SAI size_t _binbuddy_sizeof(mreq_t *req, const mlfunc_t * cont, buddy_conf_t *conf, INFUN(buddy_cobj, cobj)){
	/* 常量折叠可以优化这个判断 */
	// if (cont->lmaxsize == -1UL){
	// 	uvoid *uptr = req->ptr;
	// 	req->ptr = cobj->uptr2ptr(uptr, &req->size);
	// 	/* 可用大小 */
	// 	req->size -= cobj->mocupysz();
	// }else{
		/* 对齐 */
		BUDDY_PRINT("[binbuddy] sizeof req->ptr %p\n", req->ptr);
		// if (((paddr_t)req->ptr & (cont->lmaxsize - 1))){
		// 	/* BUDDY_PRINT("[binbuddy] sizeof req->ptr %p\n", req->ptr); */
		// 	uvoid *uptr = req->ptr;
		// 	req->ptr = cobj->uptr2ptr(uptr, &req->size);
		// 	/* 可用大小 */
		// 	req->size -= cobj->mocupysz();
		// }
		/* 查询 */
		/* printf("[%u][try free %p]\n", mtls_by_req(req)->apdstls.tinfo.tid, req->ptr); */
		if (MLAYER_IS_LASTLAYER(cont) || is_ptr_aligned(req->ptr, conf->min_size)){
			uvoid *uptr = req->ptr;
			void *ptr = cobj->uptr2ptr(uptr);
			size_t sz = cobj->ptr_getsize(ptr);
			BUDDY_PRINT("[binbuddy] sizeoof %p is %lx\n", ptr, sz);
			
			/* __DEBUG_ASSERT_DOSTH(is_aligned(sz, 0x10000), dbg_printf("sizeof err size %lx\n", sz)); */
			ASSERT(sz != 0);
			// if (sz != 0){
				/* __DEBUG_ASSERT_DOSTH(is_aligned(sz, 0x10000), dbg_printf("sizeof err size %lx\n", sz)); */
				BUDDY_PRINT("[binbuddy] sizeoof %p is %lx\n", ptr, sz);
				req->ptr = ptr;
				// req->usize = sz - cobj->mocupysz();
				req->size = sz;
				return sz - cobj->mocupysz();
			// }
/* 			else{
				sz == 0 说明是上层申请
				fatal("%p sz equal to zero??\n", req->ptr);
			} */
		}
	/* fatal("should not be here!!?? %p %lx\n", req->ptr, min_size); */
	// }
	return cont->lsizeof(req);
}


/* buddy 
	- pbuddy : 外部状态变量指针
	单线程
*/
#define DEF_BUDDYEXT_MLAYER(name, pbuddy, minbit, maxbit, oom_allocbit, oalloc) \
DEF_MLAYER_BASIC(name, BIT(maxbit), 0)\
DEF_CLS_POW2B(name##_cls, minbit, maxbit)\
static cobj_ord_t *name##pmap;\
COBJ_EXT(name##ext, name##pmap, BIT(minbit))\
DEF_BUDDY_CRTISEC(name, name##ext, name##_cls, BINBUDDY_APDS, _clsnr_##name##_cls, BIT(maxbit))\
static const buddy_conf_t name##_conf = { .min_size = BIT(minbit), .oom_allocsize = BIT(oom_allocbit), .total_szcls = _clsnr_##name##_cls};\
/* 必须初始化外部pmap */\
SAI void name##_pinit(const mlfunc_t * cont){ if (!name##pmap) {\
	name##pmap = oalloc(BIT(HDEF_PTR_BITS)/BIT(minbit)); }\
	return _binbuddy_pinit(cont); }\
SAI void name##_tinit(const mlfunc_t * cont){\
	/* 无论是单一堆还是分离堆，在线程开始应该初始化 */\
	if (pbuddy == NULL_PTR){\
		size_t size = sizeof(buddy_obj_t) + (_clsnr_##name##_cls + 1) * sizeof(dlist_t);\
		void *buddymem = oalloc(size); \
		pbuddy = __binbuddy_init(buddymem, size, _clsnr_##name##_cls, OUFUN_OF(BINBUDDY_APDS));\
	}\
	return _binbuddy_tinit(cont, pbuddy); }\
SAI void *name##_alloc(mreq_t *req, const mlfunc_t * cont){\
	return _binbuddy_alloc(req, cont, pbuddy, &name##_conf, OUFUN_OF(name##_cls), OUFUN_OF(name##ext), INFUN_OF(name##_critsec));\
}\
SAI bool_t name##_free(mreq_t *req, const mlfunc_t * cont){\
	return _binbuddy_free(req, cont, pbuddy, OUFUN_OF(name##_cls), OUFUN_OF(name##ext), INFUN_OF(name##_critsec));\
}\
SAI size_t name##_sizeof(mreq_t *req, const mlfunc_t * cont){\
	return _binbuddy_sizeof(req, cont, &name##_conf, OUFUN_OF(name##ext));\
}

/* 锁形式 */
